package tree.binarySortTree;

/** 二叉排序树 */
public class BinarySortTreeDemo {

  public static void main(String[] args) {
    int[] arr = {7, 3, 10, 12, 5, 1, 9,2};
    BinarySortTree binarySortTree = new BinarySortTree();
    for (int a : arr) {
      binarySortTree.add(new Node(a));
    }
    binarySortTree.midOrder();

    binarySortTree.delNode(1);
    System.out.println("删除以后");
    binarySortTree.midOrder();

  }
}

class BinarySortTree {
  Node root;

  public void add(Node node) {
    if (root != null) {
      root.add(node);
    } else {
      root = node;
    }
  }

  public void midOrder() {
    if (root==null){
      System.out.println("空树");
    }else{
      root.minOrder();
    }
  }

  //查找结点
  public Node search(int value) {
    if (root==null){
      return null;
    }else {
      return root.search(value);
    }
  }

  //查找 结点的父结点
  public Node searchParent(int value){
    if (root==null){
      return null;
    }else {
      return root.searchParent(value);
    }
  }

  /**
   *
   * @param node 传入的结点(当做二叉排序树的根结点)
   * @return 返回的 以node 为根结点的二叉排序树的最小结点的值
   */
  public int delRightTreeMin(Node node) {
    Node target = node;
    //循环的查找左子节点，就会找到最小值
    while(target.left != null) {
      target = target.left;
    }
    //这时 target就指向了最小结点
    //删除最小结点
    delNode(target.value);
    return target.value;
  }

  //删除指定结点
  public void delNode(int value){
    if (root==null){
      return;
    }else {
      Node targetNode = root.search(value);
      if (targetNode==null){
        return;
      }
      //该树仅有一个root结点
      if (root.left==null&&root.right==null){
        root=null;
      }
      Node parent = root.searchParent(value);

      //1.删除的是叶子结点
      if (targetNode.left==null&&targetNode.right==null){
        if (parent.left!=null&&parent.left.value==value){//该结点为父结点的左子结点
          parent.left=null;
        }else if (parent.right!=null&&parent.right.value==value){//该结点为父结点的右子结点
          parent.right=null;
        }
        //2.删除有两颗子树的结点
      }else if(targetNode.left!=null&&targetNode.right!=null){
        int minVal = delRightTreeMin(targetNode.right);
        targetNode.value = minVal;

        //3.删除只有一颗子树的结点
      }else {
        //要删除的结点有左子结点
        if (targetNode.left!=null){
          if (parent.left.value==value){//如果targetNode是parent的左子结点
            parent.left=targetNode.left;
        }else { //如果targetNode是parent的右子结点
            parent.right=targetNode.left;
          }
          //要删除的结点有右子结点
      }else {
          if (parent.left.value==value){//如果targetNode是parent的左子结点
            parent.left=targetNode.right;
          }else { //如果targetNode是parent的右子结点
            parent.right=targetNode.right;
          }
        }
        }
    }
  }
}

class Node {
  int value;
  Node left;
  Node right;
  @Override
  public String toString() {
    return "Node{" + "value=" + value + '}';
  }

  public Node(int value) {
    this.value = value;
  }

  public void add(Node node) {
    if (node.value < this.value) {
      if (this.left == null) {
        this.left = node;
      } else {
        this.left.add(node);
      }
    } else {
      if (this.right == null) {
        this.right = node;
      } else {
        this.right.add(node);
      }
    }
  }


  //左旋转方法
  private void leftRotate() {

    //创建新的结点，以当前根结点的值
    Node newNode = new Node(value);
    //把新的结点的左子树设置成当前结点的左子树
    newNode.left = left;
    //把新的结点的右子树设置成带你过去结点的右子树的左子树
    newNode.right = right.left;
    //把当前结点的值替换成右子结点的值
    value = right.value;
    //把当前结点的右子树设置成当前结点右子树的右子树
    right = right.right;
    //把当前结点的左子树(左子结点)设置成新的结点
    left = newNode;


  }

  //右旋转
  private void rightRotate() {
    Node newNode = new Node(value);
    newNode.right = right;
    newNode.left = left.right;
    value = left.value;
    left = left.left;
    right = newNode;
  }

  /**
   * 根据值查找该结点
   * @param value
   * @return
   */
  public Node search(int value){
    if (this.value==value){
      return this;
    }else if (value<this.value){
      if (this.left==null){
        return null;
      }
      return this.left.search(value);
    }else{
      if (this.right==null){
        return null;
      }
      return this.right.search(value);
    }
  }

  /**
   * 根据值查找该结点的父结点
   * @param value
   * @return
   */
  public Node searchParent(int value){
    if ((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
      return this;
    }else {
      if (this.left!=null&&value<this.value){
        return this.left.searchParent(value);
      }else if (this.right!=null&&value>=this.value){
        return this.right.searchParent(value);
      }else {
        return null;//没有找到父结点
      }
    }
  }

  public void minOrder() {
    if (this.left != null) {
      this.left.minOrder();
    }
    System.out.println(this);
    if (this.right!=null){
      this.right.minOrder();
    }
  }
}
